import java.util.*;

public class NQueens {
}
class NQueensSolution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList();
        dfs(res,n,new ArrayList(),0);
        return res;
    }
    boolean isValid(List<Integer> list,int c,int l){
        for(int i=0;i<list.size();i++){
            if((Math.abs(i-c)==Math.abs(l-list.get(i)))||list.get(i)==l)return false;
        }
        return true;
    }
    void dfs(List<List<String>> res,int n,List<Integer> list,int r){
        if(r==n){
            List<String> tmp = new ArrayList();
            for(int i=0;i<n;i++){
                String str = "";
                for(int j=0;j<n;j++){
                    if(list.get(i)!=j)
                        str+=".";
                    else
                        str+="Q";
                }
                tmp.add(str);
            }
            res.add(new ArrayList(tmp));
            return;
        }
        for(int i=0;i<n;i++){
            if(isValid(list,r,i)){
                list.add(i);
                dfs(res,n,list,r+1);
                list.remove(list.size()-1);
            }
        }
    }
}